
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    /**
     * 第一遍
     * 执行耗时:5 ms,击败了69.01% 的Java用户
     * 内存消耗:41.4 MB,击败了56.06% 的Java用户
     * @param s
     * @return
     */
//    public String reverseWords(String s) {
//        // 清洗数据
//        StringBuilder sb = new StringBuilder();
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if (c != ' ') {
//                sb.append(c);
//                // sb不为空且末尾也不为空时
//            } else if (!sb.isEmpty() && sb.charAt(sb.length() - 1) != ' ') {
//                sb.append(' ');
//            }
//        }
//
//        // 清除末尾空格
//        if (sb.charAt(sb.length() - 1) == ' ') {
//            sb.deleteCharAt(sb.length() - 1);
//        }
//
//        // 清洗之后的字符串
//        char[] chars = sb.toString().toCharArray();
//        int n = chars.length;
//        // 整体反转单词数组
//        reverse(chars, 0, n - 1);
//        // 再把每个单词单独反转
//        for (int i = 0; i < n;) {
//            for (int j = i; j < n; j++) {
//                // 到了末尾或者遇到空格时，都要将i-j个单词进行反转
//                if (j + 1 == n || chars[j+1] == ' ') {
//                    reverse(chars, i, j);
//                    // 把i设置为下一个单词的首字母,因为j+1是''
//                    i = j + 2;
//                    break;
//                }
//            }
//        }
//        return new String(chars);
//    }
//
//
//    // 从start-end反转字符数组
//    void reverse(char[] chars, int start, int end) {
//        while (start < end) {
//            char temp = chars[start];
//            chars[start] = chars[end];
//            chars[end] = temp;
//            start++;
//            end--;
//        }
//    }


    /**
     * 第二遍
     * 执行耗时:5 ms,击败了69.01% 的Java用户
     * 内存消耗:41 MB,击败了95.93% 的Java用户
     * @param s
     * @return
     */
//    public String reverseWords(String s) {
//        // 清洗数据
//        StringBuilder sb = new StringBuilder();
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if (c != ' ') {
//                sb.append(c);
//            } else if (!sb.isEmpty() && sb.charAt(sb.length() - 1) != ' ') {
//                sb.append(' ');
//            }
//        }
//
//        // 去除多余空格
//        if (sb.charAt(sb.length() - 1) == ' ') {
//            sb.deleteCharAt(sb.length() - 1);
//        }
//
//        // 转换成字符数组再整体进行反转
//        char[] chars = sb.toString().toCharArray();
//        int n = chars.length;
//        reverse(chars, 0 , n - 1);
//        // 再根据空格的间隔进行单词的单个反转
//        int fast = 0, slow = 0;
//        while (fast < n) {
//            if (chars[fast] == ' ') {
//                reverse(chars, slow, fast - 1);
//                slow = fast + 1;
//            }
//            fast++;
//        }
//        // 由于最后一个单词没有空格，单独处理下
//        reverse(chars, slow, n - 1);
//        return new String(chars);
//    }
//
//    void reverse(char[] chars, int start, int end) {
//        while (start < end) {
//            char temp = chars[end];
//            chars[end] = chars[start];
//            chars[start] = temp;
//            start++;
//            end--;
//        }
//    }

    /**
     *  第三遍 2/27
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        // 清洗数据，将多余的空格去掉
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != ' ') {
                sb.append(c);
            } else if (!sb.isEmpty() && sb.charAt(sb.length() - 1) != ' ') {
                sb.append(' ');
            }
        }

        // 去除末尾的空格
        if (sb.charAt(sb.length() - 1) == ' ') {
            sb.deleteCharAt(sb.length() - 1);
        }

        // 转换成字符数组，再进行整体反转
        char[] chars = sb.toString().toCharArray();
        int n = chars.length;
        reverse(chars, 0, n - 1);

        // 再根据空格的间隔进行单词的反转
        int slow = 0,  fast = 0;
        while (fast < n) {
            if (chars[fast] == ' ') {
                reverse(chars, slow, fast - 1);
                slow = fast + 1;
            }
            fast++;
        }

        // 最后处理下最后一个单词
        reverse(chars, slow, n - 1);
        return new String(chars).trim();
    }

    void reverse(char[] chars, int slow, int fast) {
         while (slow < fast) {
             char temp = chars[fast];
             chars[fast] = chars[slow];
             chars[slow] = temp;
             slow++;
             fast--;
         }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
